package com.zp.self.module.level_4_算法练习.数据结构.设计结构;

import java.util.Arrays;
import java.util.Random;

/**
 * @author By ZengPeng
 */
public class 力扣_384_打乱数组 {
    //测试
    public static void main(String[] args) {

        Solution obj = new Solution(new int[]{1, 2, 3,4,5,6,7,8,9});
        obj.shuffle();

        int[] param_1 = obj.reset();
        System.out.println(Arrays.toString(param_1));

        int[] param_2 ;
        for (int i = 0; i < 100; i++) {
            param_2  = obj.shuffle();
            System.out.println(Arrays.toString(param_2));
        }
        param_1 = obj.reset();
        System.out.println(Arrays.toString(param_1));

    }

    /**
    题目：给你一个整数数组 nums ，设计算法来打乱一个没有重复元素的数组。打乱后，数组的所有排列应该是 等可能 的。

     实现 Solution class:

     Solution(int[] nums) 使用整数数组 nums 初始化对象
     int[] reset() 重设数组到它的初始状态并返回
     int[] shuffle() 返回数组随机打乱后的结果
      

     示例 1：
     输入
     ["Solution", "shuffle", "reset", "shuffle"]
     [[[1, 2, 3]], [], [], []]
     输出
     [null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]
     解释
     Solution solution = new Solution([1, 2, 3]);
     solution.shuffle();    // 打乱数组 [1,2,3] 并返回结果。任何 [1,2,3]的排列返回的概率应该相同。例如，返回 [3, 1, 2]
     solution.reset();      // 重设数组到它的初始状态 [1, 2, 3] 。返回 [1, 2, 3]
     solution.shuffle();    // 随机返回数组 [1, 2, 3] 打乱后的结果。例如，返回 [1, 3, 2]

    分析：【P 💜💜💜】
       1.二分法random ：得到的当前值，两边继续random,不行啊，会有相对顺序的
       2.random ：遍历数组，每次随机生成一个下标，让两个下标位置互换
             注意：1.使用成员变量记录初始值，这个是必须的
                   2.使用成员变量记录随机值，主要是每次创建的内存
             --执行用时：48 ms, 在所有 Java 提交中击败了96.87%的用户
             --内存消耗：47.3 MB, 在所有 Java 提交中击败了84.72%的用户

    边界值 & 注意点：
       1.
     **/
}
class Solution {
    int[] init ;
    int[] shuffle ;
    int length ;
    Random random = new Random();

    public Solution(int[] nums) {
        init = nums;
        length= init.length;
        shuffle = new int[init.length];
        System.arraycopy(nums,0,shuffle,0,init.length);
    }
    public int[] reset() {
        return init;
    }
    public int[] shuffle() {
        for (int i = 0; i < length; i++) {
            int index = random.nextInt(length);
            if(index==i)continue;
            shuffle[i] = shuffle[i]^shuffle[index];
            shuffle[index] = shuffle[i]^shuffle[index];
            shuffle[i] = shuffle[i]^shuffle[index];
        }
        return shuffle;
    }
}